/*
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }

}
*/
import java.util.*;

public class Solution {
    boolean recursion(TreeNode l, TreeNode r) {
        if (l == null && r == null) {
            return true;
        }

        if (l == null || r == null || l.val != r.val) {
            return false;
        }

        return recursion(l.left, r.right) && recursion(l.right, r.left);
    }

    boolean isSymmetrical(TreeNode pRoot) {
        // 递归
        /*
        return recursion(pRoot, pRoot);
        */

        // 队列
        if (pRoot == null) {
            return true;
        }

        Queue<TreeNode> lQ = new LinkedList<>();
        Queue<TreeNode> rQ = new LinkedList<>();
        lQ.add(pRoot.left);
        rQ.add(pRoot.right);

        while (!lQ.isEmpty() && !rQ.isEmpty()) {
            TreeNode l = lQ.remove();
            TreeNode r = rQ.remove();

            if (l == null && r == null) {
                continue;
            }

            if (l == null || r == null || l.val != r.val) {
                return false;
            }


            lQ.add(l.left);
            lQ.add(l.right);

            rQ.add(r.right);
            rQ.add(r.left);
        }
        return true;
    }
}
